#ifndef TIM_BINTREE_H
#define TIM_BINTREE_H
#include<bits/stdc++.h>
#include"tim_stack&tim_queue.h"

namespace tim
{
	template<typename T>
	class binnode
	{
		public:
			T data;
			binnode<T>* parent;
			binnode<T>* left;
			binnode<T>* right;
			bool mark;
			int height;
			binnode(): data((T)0), parent(NULL), left(NULL), right(NULL), mark(false), height(0) {};
			binnode(T const& d, binnode<T>* p = NULL, binnode<T>* l = NULL, binnode<T>* r = NULL, bool m = false, int h = 0):
			data(d), parent(p), left(l), right(r), mark(m), height(h) {};
			int size();
			binnode<T>* insert_left(T const& e);
			binnode<T>* insert_right(T const& e);
			binnode<T>* insert_left(binnode<T>* l);
			binnode<T>* insert_right(binnode<T>* r);
			binnode<T>* insert_parent(binnode<T>* p);
			binnode<T>* succ();//直接后继
			template<typename VST>
			void level_traverse(VST& visit);//子树递归层次便历
			template<typename VST>
			void pre_traverse(VST& visit);//子树递s归前序遍历
			template<typename VST>
			void post_traverse(VST& visit);//子树递归后序遍历
			template<typename VST>
			void in_traverse(VST& visit);//子树递归中序遍历
			bool is_root() {return parent == NULL; };
			bool is_lchild(binnode<T>* _parent) {return _parent->left->data == data;}
			bool is_rchild(binnode<T>* _parent) {return _parent->right->data == data;}
			bool is_sibling(binnode<T>* another) {return another->parent == parent;}
			bool is_leaf() {return left == NULL and right == NULL;}
			bool is_uncle(binnode<T>* uncle) {return uncle->parent == parent->parent;}
			bool has_root() {return parent != NULL; } // 简化语义判断
			bool has_lchild() {return left != NULL;}
			bool has_rchild() {return right != NULL; }
			bool has_child() {return (left != NULL or right != NULL);}
			bool has_both_child() {return left != NULL and right != NULL;}
	};

	template<typename T>
	class bintree
	{
		protected:
			int _size;
			binnode<T>* root;
			virtual void update_height(binnode<T>* x);
			void update_height_above(binnode<T>* x);
			void clear(binnode<T>* x);

		public:
			bintree(): _size(0), root(NULL) {};//空生成
			bintree(T const& e): _size(1), root(new binnode<T>(e, NULL, NULL, NULL)) {};//只生成根结点
			bintree(T* begin, T* end);//层次生成
			bintree(T* begin, T* end, int height);//限制高度的中序生成
			bintree(T* begin, T* end, bool is_sort);//huffman最优树生成, false会对数组进行排序，为降序排列
			int size() { return _size;};//返回_size;
			bool is_empty() { return root == NULL;};//判空
			template<typename VST>
			void pre_traverse_re(VST& visit) { root->pre_traverse(visit); };//前序遍历递归版
			template<typename VST>
			void post_traverse_re(VST& visit) { root->post_traverse(visit); };//后序遍历递归版
			template<typename VST>
			void in_traverse_re(VST& visit) { root->in_traverse(visit); };//中序遍历递归版
			template<typename VST>
			void pre_traverse(VST& visit);//前序遍历迭代版, 时空间复杂度皆为o（n）
			template<typename VST>
			void post_traverse(VST& visit);//后序遍历迭代版, 时空间复杂度皆为o（n）
			template<typename VST>
			void in_traverse(VST& visit);//中序遍历迭代版, 时空间复杂度皆为o（n）
			template<typename  VST>
			void level_traverse(VST& visit);//层次遍历, 时空间复杂度皆为o（n）
			binnode<T>* Root() {return root; };
			binnode<T>* insert_root(T const& e) { _size++; root = new binnode<T>(e); return root;};//插入结点
			binnode<T>* insert_left_child(binnode<T>* x, T const& e);//插入左右子结点
			binnode<T>* insert_right_child(binnode<T>* x, T const& e);//
			bintree<T>& insert_left_tree(binnode<T>* x, bintree<T>& l);//插入左右子树
			bintree<T>& insert_right_tree(binnode<T>* x, bintree<T>& r);//插入
			bintree<T>& secede(binnode<T>* x);//将子树x从树中拨离
			~bintree() { clear(root); };
	};
}

template<typename T>
tim::binnode<T>* tim::binnode<T>::insert_left(T const& e)
{
	binnode<T>* new_one = new binnode<T>(e, this);
	left = new_one;
	return new_one;
}

template<typename T>
tim::binnode<T>* tim::binnode<T>::insert_right(T const& e)
{
	binnode<T>* new_one = new binnode<T>(e, this);
	right = new_one;
	return new_one;
}

template<typename T>
tim::binnode<T>* tim::binnode<T>::insert_left(binnode<T>* l)
{
	if (right == NULL) height++;
	this->left = l;
	this->left->height = this->height - 1;
	return l;
}

template<typename T>
tim::binnode<T>* tim::binnode<T>::insert_right(binnode<T>* r)
{
	if (left == NULL) height++;
	this->right = r;
	this->right->height = this->height - 1;
	return r;
}

template<typename T>
template<typename VST>
void tim::binnode<T>::pre_traverse(VST& visit)
{
	if (this == NULL) return;
	visit(data);
	left->pre_traverse(visit);
	right->pre_traverse(visit);
}

template<typename T>
template<typename VST>
void tim::binnode<T>::in_traverse(VST& visit)
{
	if (this == NULL) return;
	left->in_traverse(visit);
	visit(data);
	right->in_traverse(visit);
}

template<typename T>
template<typename VST>
void tim::binnode<T>::post_traverse(VST&visit)
{
	if (this == NULL) return;
	left->post_traverse(visit);
	right->post_traverse(visit);
	visit(data);
}

template<typename T>
tim::bintree<T>::bintree(T* begin, T* end)
{
	root = new binnode<T>(begin[0]);
	int cnt = 1;
	tim::queue<binnode<T>*> wait;
	wait.enqueue(root);
	_size = 1;
	int l = end - begin;

	while (cnt < l) {
		binnode<T>* temp_parent = wait.dequeue();
		wait.enqueue(insert_left_child(temp_parent, begin[cnt++]));
		if (cnt < l) wait.enqueue(insert_right_child(temp_parent, begin[cnt++]));
	}
}

template<typename T>
void tim::bintree<T>::update_height(binnode<T>* x)
{
	if (x->left == NULL and x->right == NULL)
		return;

	if (x->left != NULL and x->right != NULL)
		x->height = 1 + (x->left->height > x->right->height? x->left->height: x->right->height);

	if (x->left == NULL)
		x->height = 1 + x->right->height;

	if (x->right == NULL)
		x->height = 1 + x->left->height;
}

template<typename T>
void tim::bintree<T>::update_height_above(binnode<T> *x)
{
	while (x != NULL) {
		update_height(x);
		x = x->parent;
	}
}

template<typename T>
tim::binnode<T>* tim::bintree<T>::insert_left_child(binnode<T> *x, T const&e)
{
	_size++;
	x->insert_left(e);
	update_height_above(x);
	return x->left;
}

template<typename T>
tim::binnode<T>* tim::bintree<T>::insert_right_child(binnode<T> *x, T const&e)
{
	_size++;
	x->insert_right(e);
	update_height_above(x);
	return x->right;
}

template<typename T>
tim::bintree<T>& tim::bintree<T>::insert_left_tree(binnode<T>* x, bintree<T>& l)
{
	_size += l.size();
	x->left = l.root;
	update_height_above(x);
	return l;
}

template <typename T>
tim::bintree<T>& tim::bintree<T>::insert_right_tree(binnode<T>* x, bintree<T>& r)
{
	_size += r.size();
	x->right = r.root;
	update_height_above(x);
	return r;
}

template<typename T>
tim::bintree<T>& tim::bintree<T>::secede(binnode<T>* now)
{
	binnode<T>* temp_parent = now->parent;
	now->parent = NULL;
	bintree<T> new_tree = *(new bintree<T>);
	new_tree->root = now;
	return new_tree;
}

template <typename T>
tim::bintree<T>::bintree(T* begin, T* end, bool is_sort)
{
	if (!is_sort);//wait
	int s = end - begin;
	tim::list<bintree<T>*> subtrees;
	for (int i = 0; i < s; i++) {
		bintree<T>* temp = new bintree<T>(begin[i]);
		subtrees.insert_back(temp);
	}

	while (subtrees.size() > 1) {
		bintree<T>* temp_tree = new bintree<T>(subtrees[0]->root->data + subtrees[1]->root->data);
		temp_tree->insert_left_tree(temp_tree->root, *subtrees[0]);
		temp_tree->insert_right_tree(temp_tree->root, *subtrees[1]);
		subtrees.remove_front();
		subtrees.remove_front();

		if (subtrees.size() > 0) {
			for (int i = 0; ; i++)
				if (subtrees[i]->root->data > temp_tree->root->data) {
					subtrees.insert(i, temp_tree);
					break;
				}
				else if (i == subtrees.size() - 1) {
					subtrees.insert_back(temp_tree);
					break;
				}
		}
		else subtrees.insert_front(temp_tree);
	}
	this->root = subtrees[0]->root;
	this->_size = subtrees[0]->_size;
}

template<typename T>
template<typename VST>
void tim::bintree<T>::pre_traverse(VST &visit)
{
	tim::stack<binnode<T>*> wait;
	binnode<T>* x = root;

	while (true) {
		while (x != NULL) {
			visit(x->data);
			if(x->right != NULL) wait.push(x->right);
			x = x->left;
		}//遍历到最深的左子树
		if (wait.empty()) break;
		x = wait.pop();
	}
}

template<typename T>
template<typename VST>
void tim::bintree<T>::in_traverse(VST& visit)
{
	tim::stack<binnode<T>*> wait;
	binnode<T>* x = root;

	while (true) {
		while (x != NULL) {
			wait.push(x);
			x = x->left;
		}
		if (wait.empty()) break;
		x = wait.pop();
		visit(x->data);
		x = x->right;
	}
}

template<typename T>
template<typename VST>
void tim::bintree<T>::post_traverse(VST &visit)
{
	tim::stack<binnode<T>*> wait;
	binnode<T>* x = root;
	wait.push(x);

	while (!wait.empty()) {
		if (wait.top() != x->parent) {//判断有无右子树
			x = wait.top();

			while (x->has_child()) {
				if (x->has_lchild()) {
					if (x->has_rchild())
						wait.push(x->right);
					wait.push(x->left);
				}
				else if (x->has_rchild())
					wait.push(x->right);
				x = wait.top();
			}//最高左侧可见节点
		}
		x = wait.pop();
		visit(x->data);
	}
}

template<typename T>
template<typename VST>
void tim::bintree<T>::level_traverse(VST &visit)
{
	tim::queue<binnode<T>*> wait;
	wait.enqueue(root);

	while (!wait.empty()) {
		binnode<T>* x = wait.dequeue();
		visit(x->data);
		if (x->left != NULL) wait.enqueue(x->left);
		if (x->right != NULL) wait.enqueue(x->right);
	}
}

template<typename T>
void tim::bintree<T>::clear(binnode<T>* x)
{
	if (x == NULL) return;
	if (x->left != NULL) clear(x->left);
	if (x->right != NULL) clear(x->right);
	delete x;
}

template<typename T>
tim::binnode<T>* tim::binnode<T>::succ()
{
	binnode<T>* s = this;
	if (right) {
		s = right;
		while (s->has_lchild()) s = s->left;
	} else {
		while (s->is_rchild(s)) s = s->parent;
		s = s->parent;
	}
	return s;
}

#endif //TIM_BINTREE_H
